#include "hash.h"
#include "mem.h"
#include "mem_chunk.h"

typedef struct z_hash_node z_hash_node;

/* @internal
 * @brief hash table
 */
struct z_hash_table
{
  size_t size;                  /* the overall size */
  size_t nnodes;                /* number of nodes */
  z_hash_node **nodes;          /* nodes */
  z_mem_chunk *mem_chunk;       /* memory chunk for allocating nodes */
  z_hash_func *hash_func;       /* hashing function */
  z_equal_func *key_equal_func; /* key compare function */
  z_destroy_notify *key_destroy_func; /* key destroy function, may NULL */
  z_destroy_notify *value_destroy_func; /* value destroy function, my NULL */
};

/* @internal
 * @breif Node of a hash table
 */
struct z_hash_node
{
  void *key;                    /* the key */
  void *value;                  /* the value */
  z_hash_node *next;            /* the next next node */
};

/* @internal
 * Defines if a resize is necessary
 * @param hash_table a z_hash_table
 */
#define HASH_TABLE_RESIZE(hash_table)                   \
  if((hash_table->size >= 3 * hash_table->nnodes &&     \
      hash_table->size > HASH_TABLE_MIN_SIZE) ||        \
     (3 * hash_table->size <= hash_table->nnodes &&     \
      hash_table->size < HASH_TABLE_MAX_SIZE))          \
    internal_z_hash_table_resize(hash_table);

/* @internal
 * The minimal hash table size
 */
#define HASH_TABLE_MIN_SIZE 11

/* @internal
 * The maximal hash table size
 */
#define HASH_TABLE_MAX_SIZE 13845163

/* @internal
 * @param x value
 * @param low low bound
 * @param high high bound
 * @return a value between low and high
 */
#define CLAMP(x, low, high) (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))

static void internal_z_hash_table_resize(z_hash_table *hash_table);
static z_hash_node **internal_z_hash_table_lookup_node(z_hash_table *hash_table, 
                                                       const void *key);
static z_hash_node* internal_z_hash_node_new(z_hash_table *hash_table, void *key, void *value);
static void internal_z_hash_nodes_destroy(z_hash_node *hash_node, 
                                         z_destroy_notify key_destroy_func,
                                         z_destroy_notify value_destroy_func);

static unsigned int internal_z_spaced_primes_closest(unsigned int num);

z_hash_table* z_hash_table_new(z_hash_func hash_func, z_equal_func key_equal_func)
{
  return z_hash_table_new_full(hash_func, key_equal_func, NULL, NULL);
}

z_hash_table* z_hash_table_new_full(z_hash_func hash_func, z_equal_func key_equal_func,
                                    z_destroy_notify key_destroy_func, 
                                    z_destroy_notify value_destroy_func)
{
  z_hash_table *hash_table;
  size_t i;
  
  hash_table = z_new(z_hash_table, 1);
  hash_table->size = HASH_TABLE_MIN_SIZE;
  hash_table->nnodes = 0;
  hash_table->mem_chunk = z_mem_chunk_new(sizeof(z_hash_node), 4096);
  hash_table->hash_func = hash_func;
  hash_table->key_equal_func = key_equal_func;
  hash_table->key_destroy_func = key_destroy_func;
  hash_table->value_destroy_func = value_destroy_func;
  hash_table->nodes = z_new(z_hash_node *, hash_table->size);
  
  for (i = 0; i < hash_table->size; i++)
    hash_table->nodes[i] = NULL;
  return hash_table;
}

void z_hash_table_destory(z_hash_table *hash_table)
{
  size_t i;
  
  for (i = 0; i < hash_table->size; i++)
    internal_z_hash_nodes_destroy(hash_table->nodes[i], hash_table->key_destroy_func, 
                                  hash_table->value_destroy_func);
  z_mem_chunk_destroy(hash_table->mem_chunk);
  
  zfree(hash_table->nodes);
  zfree(hash_table);
}

static void internal_z_hash_nodes_destroy(z_hash_node *hash_node,
                                          z_destroy_notify key_destroy_func,
                                          z_destroy_notify value_destroy_func)
{
  if (hash_node) {
    z_hash_node *node = hash_node;
    while (node->next) {
      if (key_destroy_func)
        key_destroy_func(hash_node->key);
      if (value_destroy_func)
        value_destroy_func(hash_node->value);
      node = node->next;
    }
    if (key_destroy_func)
      key_destroy_func(hash_node->key);
    if (value_destroy_func)
      value_destroy_func(hash_node->value);
  }
}

static inline z_hash_node** internal_z_hash_table_lookup_node(z_hash_table *hash_table,
                                                              const void *key)
{
  z_hash_node **node;
  
  node = &hash_table->nodes[hash_table->hash_func(key) % hash_table->size];
  
  if (hash_table->key_equal_func)
    while (*node && !(*hash_table->key_equal_func)((*node)->key, key))
      node = &(*node)->next;
  else
    while (*node && (*node)->key != key)
      node = &(*node)->next;
  return node;
}

void *z_hash_table_lookup(z_hash_table *hash_table, const void *key)
{
  z_hash_node *node;
  
  node = *internal_z_hash_table_lookup_node(hash_table, key);
  return node ? node->value : NULL;
}

void z_hash_table_insert(z_hash_table *hash_table, void *key, void *value)
{
  z_hash_node **node;
  z_hash_node *new_node;
  new_node = internal_z_hash_node_new(hash_table, key, value);
            
  node = &hash_table->nodes[hash_table->hash_func(key) % hash_table->size];
  if (*node) { 
    new_node->next = *node; 
  }
  *node = new_node;
    
  hash_table->nnodes++;
  HASH_TABLE_RESIZE(hash_table);
}

static z_hash_node* internal_z_hash_node_new(z_hash_table *hash_table, void *key, void *value)
{
  z_hash_node *hash_node;
  
  hash_node = z_mem_chunk_alloc(hash_table->mem_chunk);
  
  hash_node->key = key;
  hash_node->value = value;
  hash_node->next = NULL;
  
  return hash_node;
}

void z_hash_table_foreach(z_hash_table *hash_table, z_hfunc *func, void *user_data)
{
  z_hash_node *node;
  size_t i;
  
  for (i = 0; i < hash_table->size; i++)
    for (node = hash_table->nodes[i]; node; node = node->next)
      func(node->key, node->value, user_data);
}

uint32_t z_hash_table_size(z_hash_table *hash_table)
{
  return hash_table->nnodes;
}

static void internal_z_hash_table_resize(z_hash_table *hash_table)
{
  z_hash_node **new_nodes;
  z_hash_node *node;
  z_hash_node *next;
  uint32_t hash_val;
  size_t new_size;
  size_t i;
  
  new_size = internal_z_spaced_primes_closest(hash_table->nnodes);
  new_size = CLAMP(new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
  
  new_nodes = z_new0(z_hash_node *, new_size);
  
  for (i = 0; i < hash_table->size; i++)
    for (node = hash_table->nodes[i]; node; node = next) {
      next = node->next;
      hash_val = (* hash_table->hash_func) (node->key) % new_size;
//      if (new_nodes[hash_val]) 
      node->next = new_nodes[hash_val];
      new_nodes[hash_val] = node;
    }
  
  zfree(hash_table->nodes);
  hash_table->nodes = new_nodes;
  hash_table->size = new_size;
}

static const unsigned int internal_z_primes[] ={  11,  19,  37,  73,  109,  163,  251,  367,  557,  823,  1237,  1861,  2777,  4177,  6247,  9371,  14057,  21089,  31627,  47431,  71143,  106721,  160073,  240101,  360163,  540217,  810343,  1215497,  1823231,  2734867,  4102283,  6153409,  9230113,  13845163,
};

static const unsigned int internal_z_nprimes = sizeof (internal_z_primes) / sizeof (internal_z_primes[0]);

static unsigned int internal_z_spaced_primes_closest (unsigned int num)
{
  unsigned int i;
  for (i = 0; i < internal_z_nprimes; i++)    
    if (internal_z_primes[i] > num)      
      return internal_z_primes[i];
  return internal_z_primes[internal_z_nprimes - 1];
}

uint32_t z_rstring_hash(const void *key)
{
  const z_rstring *rstring = key;
  const char *p = rstring->string;
  size_t n = 0;
  uint32_t h = 0;
  for (; n < rstring->size; n++)   
    h = (h << 5) - h + tolower(*p++);
  return h;
}

bool z_rstring_equal(const void *key1, const void *key2)
{
  const z_rstring *rstring1 = key1;
  const z_rstring *rstring2 = key2;
  if (rstring1->size == rstring2->size)
    return strncasecmp(rstring1->string, rstring2->string, rstring1->size) == 0;
  
  return false;
}

#ifdef DEBUGHASH
void get_key(const char *name, z_rstring *key) 
{
  size_t size;
  size = strlen (name);
  /* i know that is bad, but i know it is not written by the lookup */
  key->string = (char *) name;
  key->size = size;
}


void print (void *key, void *value, void *userdata) 
{
  z_rstring *k = key;
  
  printf("key: %s-->value:%s\n", k->string, (char *)value);
}

#include <stdio.h>
int main() 
{
  z_hash_table *table;
  int i;
  const int NUM = 1000;
  
  char str[NUM+1][10];
  z_rstring key[NUM+1];
  char str1[NUM+1][10];
  z_rstring key1[NUM+1];
  
  table = z_hash_table_new(z_rstring_hash, z_rstring_equal);
  
  for (i=0;i<NUM;i++) {
    snprintf(str[i],10,"%d",i);
    get_key(str[i],&key[i]);
    z_hash_table_insert (table, &key[i], str[i]);
  }
  snprintf(str[NUM],10,"%d",3);
  get_key(str[NUM], &key[NUM]);
  z_hash_table_insert (table, &key[NUM], str[NUM]);

  for (i=0;i<NUM;i++) {
    snprintf(str1[i],10,"%d",i);
    get_key(str1[i],&key1[i]);
    z_hash_table_insert (table, &key1[i], str1[i]);
  }

  z_hash_table_foreach(table, print, NULL);
  printf("size: %d\n", table->size);
  
  z_hash_table_destory(table);
  return 0;
}
#endif
